//二叉树的最近公共祖先
class Solution {
public:
    //思路：
    //使用后序遍历。
    //情况一 p q在不同的子树中
    //如果一个节点 他的左树包含 p|q 他的右树包含 p|q 那他就是最近的公共祖先
    //如果它的左或右子树中 包含p | q 那就把p|q 返回
    //在上层中判断是否符合最近公共祖先的情况

    //情况二 p q是在同一颗子树中 即p是q的祖先 或者 q是p的祖先
    //遇到p |q 直接返回 这样就解决了问题
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root==p || root==q || root==nullptr) return root;
        TreeNode *left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left && right) return root;
        else if(left && !right) return left;
        else if(!left && right) return right; 
        else return nullptr;
    }
};
//二叉搜索树中的众数
class Solution {
public:
    int times=0;
    TreeNode* prev=nullptr;
    int maxtime=0;
    vector<int>res;
    vector<int> findMode(TreeNode* root) 
    {
        inorder(root);
        return res;
    }
    void inorder(TreeNode* root)
    {
        if(root==nullptr) return;
        inorder(root->left);
        if(prev==nullptr)
        {
            times=1;
            prev=root;
        }
        else if(prev->val==root->val)
        {
            times++;
            prev=root;
        }
        else
        {
            times=1;
            prev=root;
        }

        if(times==maxtime)
        {
            res.push_back(root->val);    
        }

        if(times>maxtime)
        {
            maxtime=times;
            res.clear();
            res.push_back(root->val);
        }
        inorder(root->right);
        return;
    }
};